1. Field of the Invention
The present invention relates to network mapping, and more particularly to a method and system for mapping a network to make distance measurements based on delay.
2. Description of the Related Art
While Internet is growing at a remarkable rate there is no central registry that permits users or planners to track this growth. Even simple characterizations of the Internet are under debate. Learning the exact structure of the network seems to be an unrealistic target.
However, in many cases an estimate about the distances between nodes in the network is valuable. One case is the need for a client to select a service from one of several servers located in distant locations. The WWW is an example of such a situation, as more and more popular sites open mirror sites that are geographically scattered to balance not only the computation load among the servers but also the average response time to the users. Other examples where there is a need for a mechanized client selection among servers include distributed object repositories, hierarchical caching, etc.
IDMaps is an example project that attempts to solve this problem by placing measurement stations (tracers) at key locations. These tracers periodically measure the distances among themselves and to regions of the network. The tracers advertise their measurement information to clients that use the measurement information to construct an estimated distance map of the network.
A distance measurement between two IDMaps tracers can be performed in two basic ways. The first is to use the “traceroute” program, known in the art, which generates a series of packets with increasing TTL (time to live) values in their Internet protocol (IP) headers. The TTL field in the IP header is decreased by one in every router that handles the field. When the packet travels a distance equal to its initial TTL, its TTL value is decreased to zero, and the packet is dropped together with the submission of an ICMP packet from the dropping node to the packet originator.
In this way, the source node learns the id's of all the nodes on the route to some destination and the round-trip time (rtt) to this node. A second way to measure distance is by using ping. In this method, a packet is sent to the destination and replied to immediately which results in a single rtt measurement. In variants of ping, different types of packets are sent and the reply packet is sent by a dedicated application (ping) or an application whose reaction time is part of the measurement (e.g., HTTP/web-server).
It is important to note that the “traceroute” program consumes more network resources as the number of message times the number of hops of “traceroute” is quadratic in the hop distance, while ping uses a linear number of messages: one in every hop in each direction. Due to this and other reasons, ping is a preferred measurement method. However, since the route stability between two tracers is an important characteristic, the trace route program is also expected to be used but at a much lower rate than ping.
Distance estimation is important to many Internet applications, most notably for a WWW client that needs to select a server among several potential candidates. To aid in estimating distances on the Internet, conventional research suggested to place tracer stations at key locations. The tracers measure distances among themselves and use the distance measurement to supply client applications with an approximated map of the Internet. There is however a trade-off between the amount of measurement traffic and the accuracy of the mapping. The larger the number of tracers one employs, the better the estimation is, but also the measurement overhead is higher.
Therefore, a need exists for a system and method for mapping a network, which is not subject to the above-mentioned trade-off. A further need exists for a system and method for mapping a network between locations where tracers cannot be placed.